//import java.util.HashMap;
import java.util.Arrays;
//import java.util.Map;
class Solution {
    public int longestPalindromeSubseq(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        for(int i=0;i<n;i++) 
            Arrays.fill(dp[i],1);
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(s.charAt(i)==s.charAt(j))
                    dp[i][j]=(i+1==j)?2:2+dp[i+1][j-1];
                else
                    dp[i][j]=Math.max(dp[i][j-1],dp[i+1][j]);
            }
        }
        return dp[0][n-1];
    }
}